package com.LeeCode;

import javax.xml.stream.events.StartDocument;
import java.util.Arrays;

/**
 * 礼盒的最大甜蜜度
 */

public class Code2517 {
    public static void main(String[] args) {
        int[] price = {1, 3, 1};
        int k = 2;
        System.out.println(new Code2517().maximumTastiness(price, k));
    }

    public int maximumTastiness(int[] price, int k) {

        Arrays.sort(price);
        int left = 0, right = right = (price[price.length - 1] - price[0]) / (k - 1) + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check1(price, k, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(int[] price, int k, int mindiff) {
        int index = 0, previous = price[0], n = price.length;
        while (k > 1) {
            int target = previous + mindiff;
            index = lowerBound(price, index, target);
            if (index < n) {
                k--;
                previous = price[index];
            } else {
                return false;
            }
        }
        return true;
    }

    private boolean check1(int[] price, int k, int mindiff) {
        int count = 1, previous = price[0], n = price.length;
        for (int i = 1; i < n; i++) {
            int target = previous + mindiff;
            if (price[i] >= target) {
                previous = price[i];
                count++;
            }
            if (count >= k) {
                return true;
            }
        }
        return false;
    }

    private int lowerBound(int[] price, int left, int target) {
        int right = price.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (price[mid] >= target)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
}
